package dp.leetcode_518;

public class Recursion {
    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return 0;
        }
        return process(coins, 0, amount);
    }
    public int process(int[] coins, int index, int amount) {
        if (index == coins.length) {
            return amount == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int i = 0; i * coins[index] <= amount; i++) {
            ways += process(coins, index + 1, amount - i * coins[index]);
        }
        return ways;
    }

    public static void main(String[] args) {
        int[] coins = new int[] {5, 2, 3};
        int amount = 10;
        new Recursion().coinChange(coins, amount);
    }
}
